package 数组;

public class SolutionDemo06 {
    /*
    * 第一种解法 : 遍历数组,将前一个位置的元素拷贝到后面,时间超过限制
    * 第二种解法 : 使用一个新的数组来接受,典型的空间换时间(不推荐)
    * */
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        k%=len;
        int[] arr = new int[len];
        int j = 0;
        for(int i = len-k; i<len ;i++){
            arr[j++] = nums[i];
        }

        for(int i = 0; i < len-k ;i++){
            arr[j++] = nums[i];
        }

        System.arraycopy(arr, 0, nums, 0, len);
    }

    /*
    * 环状替代 https://leetcode.cn/problems/rotate-array/ 推荐
    * */
    static class Solution1 {
        public void rotate(int[] nums, int k) {
            int len  = nums.length;
            k = k % len;
            int count = 0;         // 记录交换位置的次数，n个同学一共需要换n次
            for(int start = 0; count < len; start++) {
                int cur = start;       // 从0位置开始换位子
                int pre = nums[cur];
                do{
                    int next = (cur + k) % len;
                    int temp = nums[next];    // 来到角落...
                    nums[next] = pre;
                    pre = temp;
                    cur = next;
                    count++;
                }while(start != cur)  ;     // 循环暂停，回到起始位置，角落无人

            }
        }
    }

    /*
    * 旋转数组(反转数组)  推荐
    * 先经过一次大的反转,在经过两次小的反转
    * */
    static class Solution {
        public void rotate(int[] nums, int k) {
            k = k % nums.length;
            rotateChild(nums,0,nums.length-1);
            rotateChild(nums,0,k-1);
            rotateChild(nums,k,nums.length-1);
        }

        public void rotateChild(int[] arr,int begin,int tail){
            while(begin < tail){
                int temp = arr[begin];
                arr[begin] = arr[tail];
                arr[tail] = temp;
                begin++;
                tail--;
            }
        }
    }

}

